package com.ai.zuochengyun.phase01.class03;

import java.util.Stack;

/**
 * 非递归遍历
 */
public class Code12_UnRecursiveTraversalBT {
    public static void main(String[] args) {

    }

    /**
     * 先序遍历
     * @param head
     */
    public static void pre(BinaryTreeNode head) {
        if (head == null) {
            return;
        }
        Stack<BinaryTreeNode> stack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()) {
            // 栈顶出来，记为cur
            BinaryTreeNode cur = stack.pop();
            System.out.println(cur.value);
            // 有右先压入右，有左先压入左
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
    }


    /**
     * 中序遍历
     * 节点不为空的时候，就压入栈，来到叶子节点后，就开始弹出
     * @param head
     */

    public static void in(BinaryTreeNode head) {
        if (head == null) {
            return;
        }

        BinaryTreeNode cur = head;
        Stack<BinaryTreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                // 当前节点cur，以它为头的树，整个左边界都压入栈，直到遇到null节点
                stack.push(cur);
                cur = cur.left;
            } else {
                // 来到叶子节点后
                // 弹出栈顶元素打印，然后将cur定位到栈顶元素的右节点，然后继续执行第一步压栈操作
                cur = stack.pop();
                System.out.println(cur.value);
                cur = cur.right;
            }
        }
    }

    /**
     * 使用两个栈实现后序遍历
     * @param head
     */
    public static void pos(BinaryTreeNode head) {
        if (head == null) {
            return;
        }

        Stack<BinaryTreeNode> stack = new Stack<>();
        Stack<BinaryTreeNode> stack2 = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()) {
            // 栈顶出来，记为cur
            BinaryTreeNode cur = stack.pop();
            stack2.push(cur);
            // 有左先压入左，有右先压入右  // 头 右 左，  然后，从栈中弹出的时候，就变成了 左 右 头
            if (cur.left != null) {
                stack.push(cur.left);
            }
            if (cur.right != null) {
                stack.push(cur.right);
            }
        }

        // 左 右 头
        while (!stack2.isEmpty()) {
            System.out.println(stack2.pop());
        }
    }

    /**
     * 使用一个栈实现先序遍历
     * @param head
     */
    public static void pos2(BinaryTreeNode head) {
        if (head != null) {
            Stack<BinaryTreeNode> stack = new Stack<>();
            stack.push(head);
            BinaryTreeNode cur = null;
            while (!stack.isEmpty()) {
                cur = stack.peek();
                if (cur.left != null && head == cur.left && head != cur.right) {
                    stack.push(cur.left);
                } else if (cur.right != null && head != cur.right) {
                    stack.push(cur.right);
                } else {
                    System.out.println(stack.pop().value);
                    head = cur;
                }
            }
        }
    }
}
